#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/10 11:05
# @Author  : Yuyun
# @File    : 用最少的箭射爆气球.py
# @IDE     : PyCharm

"""
在二维空间中有许多球形的气球。
对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。
由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。
开始坐标总是小于结束坐标。
一支弓箭可以沿着 x 轴从不同点完全垂直地射出。
在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。
可以射出的弓箭的数量没有限制。
弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。

示例 1：
输入：points = [[10,16],[2,8],[1,6],[7,12]]
输出：2
解释：对于该样例，x = 6 可以射爆 [2,8],[1,6] 两个气球，以及 x = 11 射爆另外两个气球
示例 2：
输入：points = [[1,2],[3,4],[5,6],[7,8]]
输出：4
示例 3：
输入：points = [[1,2],[2,3],[3,4],[4,5]]
输出：2
示例 4：
输入：points = [[1,2]]
输出：1
示例 5：
输入：points = [[2,3],[2,3]]
输出：1
提示：
0 <= points.length <= 10^4
points[i].length == 2
-2^31 <= xstart < xend <= 2^31 - 1

"""

class Solution:
    """
    贪心策略
    局部最优：当气球出现重叠，一起射，所用弓箭最少；左排序后，最小右边界范围内为一只箭范围
    全局最优：把所有气球射爆所用弓箭最少。
    """

    def min_balloon_arrow(self, nums):
        #   按气球左边界排序
        nums.sort(key=lambda x:x[0])
        #   初始化左右边界
        left, right = nums[0][0], nums[0][1]
        #   默认第一个气球需要一箭
        result = 1
        #   遍历气球
        for i in range(len(nums) - 1):
            #   左边界大于最小右边界，需新箭射气球
            if nums[i + 1][0] > right:
                result += 1
                right = nums[i + 1][1]
            #   左边界小于最小右边界，气球重合，更新最小右边界
            else:
                right = min(nums[i + 1][1], right)
        return result

if __name__ == "__main__":
    balloons = eval(input().strip())
    solution = Solution()
    result = solution.min_balloon_arrow(balloons)
    print(result)